#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

class Solution{
    public:
    vector<vector<int>> ans1(vector<vector<int>>& intervals, vector<int>& newInterval){
        vector<vector<int>> ret;
        intervals.push_back(newInterval);
        sort(intervals.begin(), intervals.end());
        for(int i = 0; i != intervals.size(); i++){
            int L = intervals[i][0], R = intervals[i][1];
            if(!ret.size() || ret.back()[1] < L){
                ret.push_back({L, R});
            }else{
                ret.back()[1] = max(ret.back()[1], R);
            }
        }    
        return ret;
    }

};

void test1(){
    Solution s;
    vector<vector<int>> nums = {{1,3}, {6,9}};
    vector<int> insert = {2, 5};
    vector<vector<int>> ret = s.ans1(nums, insert);
    for(int i = 0; i != ret.size(); i++){
        cout << ret[i][0] << " " << ret[i][1] << endl;
    }
    cout << "------------------------" << endl;
}

void test2(){
    Solution s;
    vector<vector<int>> nums = {{1,2}, {3,5}, {6,7}, {8,10}, {12,16}};
    vector<int> insert = {4, 8};
    vector<vector<int>> ret = s.ans1(nums, insert);
    for(int i = 0; i != ret.size(); i++){
        cout << ret[i][0] << " " << ret[i][1] << endl;
    }
    cout << "------------------------" << endl;
}


int main(void){
    test1();
    test2();

    return 0;
}